A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
The present invention relates to communication systems and more particularly to asynchronous transfer mode (ATM) communication networks.
A communication network functions to interconnect many network users. Each user is connected to the network at a port. Typically, the network is formed by a number of interconnected nodes where information (from a user at a source) is input at an input port, is passed by the input port from node to node through the network, and is output at an output port (to a user at a destination).
Information can be communicated through a communication network in various forms. For example, time-sensitive voice, video and circuit emulation information is typically transmitted in constant bit rate (CBR) form while computer and other non-time-sensitive information is typically packetized and conmunicated in variable bit rate (VBR) form.
In communication networks, each node switches incoming information at input ports to outgoing information at output ports. For time-sensitive information, the communication through the ATM network is in CBR (constant bit rate) form and for packetized information the communication through the ATM network is in VBR (variable bit rate) form.
Fast packet switches typically can transfer hundreds of thousands of packets per second at every switch port in a communication network. Each switch port is typically designed to transfer information at a rate from 50 Mbits/s to 600 Mbit/s for broadband integrated service digital networks (ISDN). Switch sizes range from a few ports to thousands of ports.
The term "fast packet switch" includes switches capable of handling both variable-length packets of information and fixed-length packets of information. Fixed-length packets of information are desirable since they simplify the switch design. Fast packet switches using short, fixed-length packets (called "cells") are referred to as asynchronous transfer mode (ATM) switches. ATM switches connected together form an ATM network.
For ATM networks and switches, the term "packet" refers to variable-length information. Typically, a packet is hundreds and sometimes thousands of 8-bit bytes in length. For ATM networks and switches, the term "cell" refers to short (relative to packets of maximum length), fixed-length information. Typically, a cell is 53 8-bit bytes in length.
Fast packet switches are capable of handling different types of communications services in a single integrated communication network including the time-sensitive voice, video and circuit emulation information in constant bit rate (CBR) form and including computer and other non-time-sensitive information in variable bit rate (VBR) form. Although voice and video services can tolerate only a limited amount of delay and delay variance through a communication network, ATM switches are suitable for such services since they minimize delay and delay variance. ATM networks are suitable for concurrently transmitting both CBR time-sensitive and VBR non-time-sensitive information from sources to destinations through an ATM network having many differnt users.
The ATM standard for broadband ISDN networks defines a cell having a length of 53 bytes with a header of 5 bytes and data of 48 bytes. Broadband ISDN defines two transmission bit rate standards of 155M bit/s and 622M bits/s so that the cell clock periods are 2.7 microseconds and 0.68 microseconds, respectively, and the cell clock rates are 0.36M cells/sec and 1.47M cells/sec, respectively.
In a typical ATM switch, the cell processing functions are performed within the nodes of a network. Each node is an ATM switch which includes input controllers (IC's), a switch fabric (SF), output controllers (OC's) and a node control (C). The node control is used for functions including connection establishment and release, bandwidth reservation, congestion control, maintenance and network management.
In each switch, the input controllers are typically synchronized so that all cells from input controllers arrive at the switch fabric at the same time and so that cells can be accepted or rejected according to their priority. The traffic through the switch fabric is slotted and the switch fabric delay equals the sum of the timeslot duration, pipeline delay, and the queueing delay.
The node control communicates with the input controllers and the output controllers either by a direct communication path which by-passes the switch fabric or via control cells transmitted through the switch fabric.
External connections to the switch are generally bidirectional. Bidirectional connections are formed by grouping an input controller (IC) and an output controller (OC) together to form a port controller (PC).
The input sequence of cells in a virtual channel is preserved across the switch fabric so that the output sequence of cells on each virtual channel is the same as the input sequence. Cells contain a virtual channel identifier VCI in the cell header which identifies the connection to which the cell belongs. Each incoming VCI identifier in the header of each cell is translated in an input controller to specify the outgoing VCI identifier. This translation is performed in the input controller typically by table look-up using the incoming VCI identifier to address a connection table. This connection table also contains a routing field to specify the output port of the switch fabric to which the connection is routed. Other information may be included in the connection table on a per connection basis such as the priority, class of service, and traffic type of the connection.
In an ATM switch, cell arrivals are not scheduled. In a typical operation, a number of cells may arrive simultaneously at different input ports each requesting the same output port. Operations in which requests exceed the output capacity of the output port are referred to as output contention (or conflict). Since an output port can only transmit a fixed number (for example, one) cell at a time, only the fixed number of cells can be accepted for transmission so that any other cells routed to that port must either be discarded or must be buffered in a queue.
Different methods are employed for routing cells through a switch module, for example, self-routing and label routing.
A self-routing network operates with an input controller prefixing a routing tag to every cell. Typically, the input controller uses a table lookup from a routing table to obtain the routing tag. The routing tag specifies the output port to which the cell is to be delivered. Each switching element is able to make a fast routing decision by inspecting the routing tag. The self-routing network ensures that each cell will arrive at the required destination regardless of the switch port at which it enters.
A label routing network operates with a label in each cell referencing translation tables in each switching element. The label is translated in each switching element and hence any arbitrary network of switching elements may be employed.
Switches have two principal designs, time-division and space division. In a time-division switch fabric, all cells flow through a single communication channel shared in common by all input and output ports. In a space division switch, a plurality of paths are provided between the input and output ports. These paths operate concurrently so that many cells may be transmitted across the switch fabric at the same time. The total capacity of the switch fabric is thus the product of the bandwidth of each path and the average number of paths that can transmit a cell concurrently.
When the traffic load exceeds the available system resources in a network, congestion is present and performance degrades. When the number of cells is within the carrying capacity of the network, all cells can be delivered so that the number of cells delivered equals the number of cells sent without congestion. However, if cell traffic is increased to the level that nodes cannot handle the traffic, congestion results.
Congestion can be brought about by several factors. If nodes in a network are too slow to perform the various tasks required of them (queueing buffers, updating tables, etc.), queues build up, even though excess line capacity exists. On the other hand, even if nodes are infinitely fast, queues will build up whenever the input traffic rate exceeds the capacity of the output traffic rate for any particular group of outputs.
If a node has no free buffers for queuing cells, the node must discard newly arriving cells. For packet data traffic, when a cell is discarded, the packet from which the discarded cell came will be retransmitted, perhaps many times, further aggravating the congestion.
A difference exists between congestion control and flow control. Congestion control relates to insuring that each part of the network is able to carry the offered traffic. Congestion control is a network-wide consideration involving the behavior and carrying capacity of each part of the network at the time that traffic is offered to each part of the network.
Flow control, in contrast, relates to the point-to-point traffic between a given source and a given destination. Flow control insures that a source does not continually transmit data faster than the destination can receive it. Flow control generally involves direct feedback from the destination to the source to signal the source as to the availability of the destination to receive transmissions from the source.